home *** CD-ROM | disk | FTP | other *** search
/ ASME's Mechanical Engine…ing Toolkit 1997 December / ASME's Mechanical Engineering Toolkit 1997 December.iso / ai / prlg195b.lzh / GAMES.LZH / KTOUR.DOC < prev    next >
Text File  |  1987-05-15  |  7KB  |  110 lines
  1.                                THE KNIGHT'S TOUR
  2.  
  3.            The  "knight's  tour"  is  a  classic chess puzzle that may be
  4.        enjoyed and appreciated even without a deep knowledge of the  game
  5.        of  chess.   As  with so many other puzzles of lasting appeal, the
  6.        object is easy to state and understand, but finding a solution can
  7.        involve  unexpected  insights  and  ingenuity.   This  problem has
  8.        interested  many  prominent  mathematicians  since  at  least  the
  9.        nineteenth  century;  for  a survey discussion of well-known solu-
  10.        tions, see one of these:
  11.  
  12.            Mathematical Recreations & Essays, W. W.  R.  Ball,  MacMillan
  13.                 and   Co.  Ltd.   (1st  edition  was  1892,  but  it  was
  14.                 repeatedly reprinted, your library should have a copy).
  15.  
  16.            "Mathematical Games: Problems that are built on  the  knight's
  17.                 move in chess", Martin Gardner, Scientific American, Oct.
  18.                 1967, pp. 128-132.
  19.  
  20.            The object is as follows: a knight is placed on  an  arbitrary
  21.        square  on  a  chessboard, and must then be moved to visit each of
  22.        the remaining squares exactly once, eventually visiting the entire
  23.        board  without repeating any square on the path.  (A knight's move
  24.        is "L" shaped, two squares up,  down,  left  or  right,  then  one
  25.        square  in  a direction perpendicular to the first; see any intro-
  26.        ductory chess book).
  27.            There are literally millions of correct solutions, but finding
  28.        even  one  of these paths by naive trial-and-error will soon frus-
  29.        trate the impatient.  However, the Prolog language would  seem  to
  30.        be ideally suited to solving this sort of task, as a program could
  31.        arbitrarily choose successive legal knight's  moves,  backtracking
  32.        whenever  it got "stuck" in order to try new alternatives until it
  33.        covered the whole board.  The first version  of  my  program  took
  34.        this approach, but would literally run for hours without "acciden-
  35.        tally" stumbling onto even  a  single  solution  for  a  full-size
  36.        (8 by 8)  chess  board,  although  it  did  manage to find several
  37.        solutions for a smaller 5 by 5 board.
  38.            The problem was,  uninspired  guessing  led  it  to  construct
  39.        candidate  solutions that had obvious blunders in the first twenty
  40.        or so moves.  Even a moderately sophisticated human observer would
  41.        quickly  recognize  the  futility  of  attempting to complete such
  42.        paths, but the program blindly went about trying to complete  them
  43.        anyway.   True,  backtracking  would  eventually lead to a correct
  44.        solution, but this was slow,  since  it  tried  every  possibility
  45.        exhaustively.  But I am not the first to note that it is one thing
  46.        to state a logical goal and quite another for Prolog to satisfy it
  47.        in practice, especially where recursion is involved.
  48.  
  49.            To understand the approach taken by the revised program, it is
  50.        instructive first to examine one class  of  the  obvious  blunders
  51.        mentioned  above.   As  a  correct  solution  passes through every
  52.        square on the board, it  must  at  some  point  include  all  four
  53.        corners.   Choose  an arbitrary corner of a chessboard; it is easy
  54.        to convince yourself that there are only two squares  that  are  a
  55.        legal  knight's  move  away (label them A and B).  Suppose that in
  56.        constructing a candidate solution, the program  visits  square  A.
  57.        Then  if  it  does not choose to visit the corner on the next move
  58.        and continue the path via square B, it  has  committed  itself  to
  59.        ending  the  tour  in  this  corner.  (It must approach the corner
  60.        through square B at some later point in the tour.  Once there,  it
  61.        cannot  exit the corner to visit other squares, since A and B have
  62.        already been covered, and they are the only  ways  out).   If  the
  63.        program  should  similarly  commit  itself to ending in some other
  64.        corner as it attempts to trace a solution path,  then  clearly  it
  65.        has blundered, since it cannot end the solution in both places.
  66.            Considerations  such  as  this  give  rise  to the "Warnsdorff
  67.        rule," first proposed in print by the mathematician H.  C.  Warns-
  68.        dorff  in  1823.   It states that whenever you must choose between
  69.        two or more possible next moves in constructing  a  solution,  you
  70.        should  move  to  the  square that provides the fewest alternative
  71.        moves for the next turn.  Unfortunately, statements of  this  rule
  72.        by  more  contemporary  authors do not agree on whether Warnsdorff
  73.        said to "look ahead" one move or two (I have been unable to  find,
  74.        much less READ the original German).  Confronted with the "corner"
  75.        situation described above, the rule  would  likely  trace  a  path
  76.        through  the corner and back out again, and so avoid making unnec-
  77.        cessary commitments.
  78.  
  79.            My program implements the simplest form of this rule,  looking
  80.        ahead  only a single move at each step.  When faced with a choice,
  81.        it constructs a list of possibilities, beginning with those  moves
  82.        that  will lead to the fewest legal alternatives on the next move.
  83.        By trying the choices on the  list  in  this  order,  the  program
  84.        attempts  to  follow  up on those paths that are most likely to be
  85.        fruitful first, according to the Warnsdorff  rule.   If  the  rule
  86.        ranks two possible moves equally, the program chooses between them
  87.        arbitrarily.  (In practice, it picks the one  that  was  generated
  88.        first  by  the  "knight's  move"  rules  in  the database.  I have
  89.        numbered these for reference from 1 to 8, beginning at  the  upper
  90.        right,  as on a clock face.  I would love to hear from anybody who
  91.        has any thoughts on what would be the best order for listing these
  92.        rules, or who has other ideas for tie-breaking).
  93.            Although  the  extra  computation  involved  in using the rule
  94.        rather than choosing the next move arbitrarily appears to slow the
  95.        program  down,  it  will  now often find a correct solution on the
  96.        first try.  If you want, it will backtrack and try  to  find  more
  97.        alternative  solutions  by  exploring  the  remaining moves on the
  98.        sorted move list at each step.  The graphics that  accompany  this
  99.        search  process  are  a  nice  visual metaphor of the more general
  100.        Prolog backtracking search technique for satisfying complex goals.
  101.  
  102.            For instructions on running the program, read the  comment  at
  103.        the beginning of the file.  I hope you will find it enjoyable, and
  104.        will be inspired to read more in the vast  literature  surrounding
  105.        this problem.
  106.  
  107.                                          Tim Elliott
  108.                                          125 Warren Avenue
  109.                                          Rochester, NY  14618
  110.